package puzzle.projecteuler.p200;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

import astudy.util.AdvMath;

public class Problem110A {

	/**
	 * n = p_1^a_1 * ... * p_s^a_s
	 * the number of solution is [(2*a_1+1)...(2*a_s+1)+1]/2
	 * @param args
	 */
	public static void main(String[] args) {

		long start = System.currentTimeMillis();
		
		List<List<Long>> as = powers(4000000);
		for (List<Long> a: as) {
			List<Integer> b = new ArrayList<Integer>();
			for (Long x: a) b.add((int)(2*x+1));
			System.out.println(b);
		}
		
		System.out.println(find(100));
		System.out.println(find(1000));
		System.out.println(find(4000000));
		System.out.println((System.currentTimeMillis()-start) + " ms");
	}
	
	private static BigInteger find(int n) {
		
		List<List<Long>> powers = powers(2*n + 1L);
		Integer[] primes = AdvMath.primes(100);
		BigInteger min = null;
		for (int j = powers.size()-1; j > -1; j --) {
			List<Long> power = powers.get(j);
			int size = power.size();
			//compare
			boolean bCalc = true;
			if (min != null) {
				double logMin = Math.log(min.doubleValue());
				double logV = 0.0;
				for (int i = 0; i < size; i ++) {
					logV += Math.log(primes[size-i-1])*power.get(i);
				}
				if (min != null && logV > logMin + 1) {
					bCalc = false;
				}
			}
			//calculate the value
			if (bCalc) {
				BigInteger t = BigInteger.ONE;
				String f = "";
				for (int i = 0; i < size; i ++) {
					t = t.multiply(BigInteger.valueOf(primes[size-i-1]).pow(power.get(i).intValue()));
					f += ((i > 0)?" * ":"") + primes[size-i-1] + "^" + power.get(i).intValue();
					if (min != null && t.compareTo(min) > 0) {
						break;
					}
				}
				if (min == null || t.compareTo(min) < 0) {
					min = t;
					System.out.println((powers.size()-j) + "\t: " + t + "\t= " + f + " [" + ((mul(power, power.size())+1)/2) + "]" );
				}
			}
		}
		return min;
	}

	/**
	 * 计算所有满足下面条件的数组(a_1, ... a_s), s >= 1：
	 * 1) a_1 <= ... <= a_s
	 * 2) (2*a_1+1)...(2*a_{s-1}+1)(2*a_s+1) >= m
	 * 3) 数组(a_1, ... a_{s-1}, a_s-1)不能同时满足1), 2)
	 *  
	 * @param m
	 * @return
	 */
	public static List<List<Long>> powers(long m) {

		LinkedList<List<Long>> arrays = new LinkedList<List<Long>>();
		int s_max = (int)(Math.log(m)/Math.log(3.0)) + 1;
		for (int s = 1; s <= s_max; s ++) {
			Long[] a = new Long[s];
			for (int i = 0; i < s; i ++) {
				a[i] = 1L;
			}
			//获得长度为s的所有可能数组
			int w = s-1;
			while (true) {
				Long t = mul(a, s);
				if (m >= t) {
					t = t/(2*a[s-1]+1);
					if ((m-t)%(2*t) == 0) {
						a[s-1] = (m-t)/(2*t);
					} else {
						a[s-1] = (m+t)/(2*t);
					}
					//获得合法的数组
					List<Long> r = new ArrayList<Long>();
					for (Long l: a) r.add(l);
					if (!hasSmaller(arrays, r)) 
						arrays.add(r);

					//调整数组
					for (int i = a.length-1; w >= 0 && i >= w; i --) {
						a[i] = a[w]+1;
					}
					if (w < 0) {
						break;
					} else {
						continue;
					}
				} else {
					//获得合法的数组
					List<Long> r = new ArrayList<Long>();
					for (Long l: a) r.add(l);
					if (!hasSmaller(arrays, r)) 
						arrays.add(r);

					w --;
					if (w < 0) {
						break;
					} else {
						//调整数组
						for (int i = a.length-1; w >= 0 && i >= w; i --) {
							a[i] = a[w]+1;
						}
					}
				}
			}
		}
		return arrays;
	}
	
	private static boolean hasSmaller(List<List<Long>> array, List<Long> b)  {
		
		for (List<Long> a: array) {
			if (a.size() == b.size() && le(a, b)) return true;
		}
		return false;
	}
	
	/**
	 * 比较相同长度的数组
	 * 仅当a <= b时才返回true。
	 * @param a
	 * @param b
	 */
	private static boolean le(List<Long> a, List<Long> b) {

		for (int i = 0; i < a.size(); i ++) {
			if (a.get(i) > b.get(i)) return false;
		}
		return true;
	}
	
	/**
	 * 计算(2*a[0]+1) ... (2*a[k-1]+1)
	 * @param a
	 * @param k
	 * @return
	 */
	private static Long mul(Long[] a, int k) {
		
		long t = 1;
		for (int i = 0; i < k; i ++) {
			t *= (2*a[i]+1);
		}
		return t;
	}
	
	private static Long mul(List<Long> a, int k) {
		
		long t = 1;
		for (int i = 0; i < k; i ++) {
			t *= (2*a.get(i)+1);
		}

		return t;
	}
}
